﻿#include<iostream>
#include<cstdlib> 
#include<ctime>   
using namespace std;
int n;
const int N = 1e5 + 10;
int a[N];

void insert_sort()
{
	int counter = 0;
	for (int i = 2; i <= n; i++)
	{
		int key = a[i];
		int j = i - 1;
		while (j >= 1 && a[j] > key)
		{
			a[j + 1] = a[j];
			j--;
			counter++;
		}
		a[j + 1] = key;
	}

	cout << "insert_sort:"; cout << "比较次数：" << counter << "|   ";
	for (int i = 1; i <= n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl << endl;
}

void selection_sort()
{
	int counter = 0;
	for (int i = 1; i < n; i++)
	{
		int pos = i;
		for (int j = i + 1; j <= n; j++)
		{
			if (a[j] < a[pos])
			{
				pos = j;
			}
			counter++;
		}
		swap(a[i], a[pos]);
	}
	cout << "selection_sort:"; cout << "比较次数：" << counter << "|   ";
	for (int i = 1; i <= n; i++) cout << a[i] << " ";
	cout << endl << endl;
}

void bubble_sort()
{
	int counter = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n - i; j++) 
		{
			if (a[j] > a[j + 1])         
			{
				swap(a[j], a[j + 1]);
			}
			counter++;
		}
	}
	cout << "bubble_sort:"; cout << "比较次数：" << counter << "|   ";
	for (int i = 1; i <= n; i++) cout << a[i] << " ";
	cout << endl << endl;
}

void shell_sort()
{
	int counter = 0;

	// 使用 Knuth 增量序列: 1, 4, 13, 40, 121, ... (h = h*3+1)
	int h = 1;
	while (h < n / 3) h = h * 3 + 1; // 初始步长

	while (h >= 1)
	{
		// 对每个子序列进行插入排序
		for (int i = h + 1; i <= n; i++)
		{
			int key = a[i];
			int j = i - h;
			while (j >= 1 && a[j] > key)
			{
				a[j + h] = a[j];
				j -= h;
				
			}
			a[j + h] = key;
			counter++;
		}
		h /= 3; // 缩小步长
	}

	cout << "shell_sort:"; cout << "比较次数：" << counter << "|   ";
	for (int i = 1; i <= n; i++) cout << a[i] << " ";
	cout << endl<<endl;
}

int main()
{

	srand(time(0));
	cout << "生成n个随机数:";
	cin >> n;

	for (int i = 1; i <= n; i++) {
		a[i] = rand() % 100 + 1; 
	}
	/*for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}*/
	cout << "原始数组： " ;

	for(int i=1;i<=n;i++) cout << a[i] << " ";
	cout << endl;

	insert_sort();
	selection_sort();
	bubble_sort();
	shell_sort();

	return 0;
}